public List MorrisPre(Node head){
    ArrayList result=new ArrayList<>();
    Node cur=head;
    Node prev=null;

    while(cur!=null){
        if(cur.left==null){
            result.add(cur.value);
            prev=cur;
            cur=cur.right;
        }
        else{
            //find mostright
            Node node=cur.left;
            while(node.right!=null&&node.right!=cur){
                node=node.right;
            }

            if(node.right==null){
                result.add(cur.value);
                node.right=cur;
                prev=cur;
                cur=cur.left;
            }
            else{
                node.right=null;
                cur=cur.right;
            }
            
        }
    }return result;
}